package cn.yuemouren.tree.trie.leetcode;

import javax.crypto.Cipher;
import java.util.Map;
import java.util.TreeMap;

/**
 * @Author: Timi
 * @Description: TODO
 * @Date: 2020/7/11 17:45
 * @Version: v1.0
 */
public class ValidParenthesis_211 {

    private class Node {

        private boolean isLeaf;//是否是节点
        private TreeMap<Character, Node> next;//目前节点对应下面的节点

        public Node() {
            this(false);
        }

        public Node(boolean isLeaf) {
            this.isLeaf = isLeaf;
            this.next = new TreeMap<>();
        }
    }

    private Node root;//根节点
    /** Initialize your data structure here. */
    public ValidParenthesis_211() {
        this.root = new Node();
    }

    /** Adds a word into the data structure. */
    public void addWord(String word) {
        addRecursive(word,0,root);
    }

    private void addRecursive(String word, int index, Node cur){
        if (index >= word.length()){
            if(!cur.isLeaf){
                cur.isLeaf = true;
            }
            return;
        }
        if(null == cur.next.get(word.charAt(index))){
            cur.next.put(word.charAt(index),new Node());
        }
        cur = cur.next.get(word.charAt(index));
        addRecursive(word,++index,cur);
    }

    /** Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. */
    public boolean search(String word) {
        return matcher(word,0,root);
    }

    public boolean matcher(String word,int index,Node cur){
        if(index == word.length())
            return cur.isLeaf;
        char c = word.charAt(index);
        if('.' != c){
            if(cur.next.get(c) == null){
                return false;
            }
            return matcher(word,++index,cur.next.get(c));
        } else {
            for (char ch : cur.next.keySet())
                if (matcher(word,++index,cur.next.get(ch)))
                    return true;
            return false;
        }
    }

    /*public boolean matcher(String word,int index,Node cur){
        if(word.length() >= index){
            return cur.isLeaf;
        }
        char c = word.charAt(index);
        if('.' != c){
            if(null == cur.next.get(c)){
                return false;
            }
            cur = cur.next.get(c);
            return matcher(word,++index,cur);
        } else {
          for (char ch : cur.next.keySet()){
              if(matcher(word,++index,cur.next.get(ch))){
                  return true;
              }
          }
          return false;
        }
    }*/

    /**
     * ["WordDictionary","addWord","addWord","addWord","search","search","search","search"]
     * [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]]
     * @param args
     */
    public static void main(String[] args) {
        ValidParenthesis_211 data = new ValidParenthesis_211();
        data.addWord("bad");
        data.addWord("dad");
        data.addWord("mad");
        System.out.println(data.search("pad"));
        System.out.println(data.search("bad"));
        System.out.println(data.search(".ad"));
        System.out.println(data.search("b.."));

        // false
        // true
        // true
        // true
    }
    /**
     *  data.addWord("at");
     *         data.addWord("and");
     *         data.addWord("an");
     *         data.addWord("add");
     *
     *         System.out.println(data.search("a"));
     *         System.out.println(data.search(".at"));
     *         data.addWord("bat");
     *         System.out.println(data.search(".at"));
     *         System.out.println(data.search("an."));
     *         System.out.println(data.search("a.d."));
     *         System.out.println(data.search("b."));
     *         System.out.println(data.search("a.d"));
     *         System.out.println(data.search("."));
     */
}
